#include "../exercise.h"

struct Fibonacci {
    unsigned long long cache[128];
    int cached;

    // TODO: 实现正确的缓存优化斐波那契计算
    unsigned long long get(int i) {
        if (i >= 128) {
            return 0;
        }

        // 如果请求的索引已经在缓存中，直接返回
        if (i < cached) {
            return cache[i];
        }

        // 计算并缓存缺失的值
        for (int j = cached; j <= i; ++j) {
            if (j == 0) {
                cache[j] = 0;
            } else if (j == 1) {
                cache[j] = 1;
            } else {
                cache[j] = cache[j - 1] + cache[j - 2];
            }
            cached = j + 1;  // 更新已缓存的数量
        }
        return cache[i];
    }
};

int main(int argc, char **argv) {
    // TODO: 初始化缓存结构体，使计算正确
    Fibonacci fib{};
    ASSERT(fib.get(10) == 55, "fibonacci(10) should be 55");
    std::cout << "fibonacci(10) = " << fib.get(10) << std::endl;
    return 0;
}

/*
现在把计算也放到结构体了吗？


上一题：
    if (i >= 16) {
        return 0;
    }
    
    // 如果请求的索引已经在缓存中，直接返回
    if (i < cache.cached) {
        return cache.cache[i];
    }

    // 计算并缓存缺失的值
    for (int j = cache.cached; j <= i; ++j) {
        if (j == 0) {
            cache.cache[j] = 0;
        } else if (j == 1) {
            cache.cache[j] = 1;
        } else {
            cache.cache[j] = cache.cache[j - 1] + cache.cache[j - 2];
        }
        cache.cached = j + 1;  // 更新已缓存的数量
    }
    return cache.cache[i];
*/
